Apparatuses and methods consistent with exemplary embodiments relate to modular multipliers and a modular multiplication method thereof.
An operation performed in a public key crypto algorithm such as a Rivest Shamir Adleman (RSA) and an elliptic curve cryptography (ECC) is based on a modular operation. As a basic operation of the modular operation, there are a modular addition/subtraction and a modular multiplication. A modular division is not used in many algorithms because the quantity of calculations in a modular division is very large. In some cases, a modular division is calculated using a modular multiplication. A modular multiplication can be calculated by sets of modular additions. This case corresponds to a serialized multiplication and thereby its operation speed is very low. Thus, to improve performance, a modular multiplication increases a radix to be realized in a digit-serialized multiplication form.
Accordingly, operations basically performed in a public key operational unit are a modular addition/subtraction and a modular multiplication. Since a modular multiplication operation is more complicated than a modular addition/subtraction operation and a critical path of the modular multiplication operation is longer than that of the modular addition/subtraction operation, the maximum frequency of the whole secure operational unit depends on how a modular multiplication is embodied.
A modular multiplication algorithm includes two operations. The two operations are a multiplication operation and a reduction operation. A modular multiplication algorithm widely used in a hardware design is a Montgomery multiplication algorithm. The Montgomery multiplication algorithm can effectively perform a reduction operation.
The Montgomery multiplication algorithm performs a reduction determination or a quotient generation as one process of execution. If radix is small (e.g., 2 or 4), a reduction determination can be simply calculated. However, to increase a performance speed of a public key operational unit, the size of a digit is inevitably increased. At this time, a reduction determination becomes complicated and, thereby, a part for the reduction determination occupies a large portion of a critical path. This not only reduces a performance speed of the public key operation but also acts as the limit of radix increase.